//
//  main.c
//  Questions
//
//  Created by wangrui on 14-09-18.
//  Copyright (c) 2014年 PPS. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

void printArray(int a[], int count)
{
	for (int k=0; k<count; k++) {
		printf("%d ",a[k]);
	}
	
	printf("\n");
}

void swap(int *a, int  *b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

/*
 *输入n, 寻求1-n的全排列
 *eg: 
 *in: n =  3
 *out: 123 132 213 231 312 321
 *
 *可利用图的方法来解决，把每个元素构想成一个点，深度遍历每一个点
 *抽象为往盒子里放牌的模型
 *
 *此类要遍历，又要回溯的问题，可以考虑这种解法
 */

int values[10]; int boxeFlags[10]; int n;

void dfs(int step)
{
	if (step == n + 1 ) {
		printArray(values+1, n); //打印从第一个开始
		return;
	}
	
	for (int i = 1; i <= n; i++) {
		
		if ( boxeFlags[i] == 0) {//第i号盒子里没有牌
			values[step] = i;
			boxeFlags[i] = 1;
			
			dfs(step+1);
			boxeFlags[i] = 0;
		}
	}
	
}

int main(int argc, const char * argv[])
{
	scanf("%d",&n); //n 输1到9
	
	dfs(1);
	
	return 0;
}


